﻿//
//  main.cpp
//  树forXcode
//
//  Created by asus on 2020/7/6.
//  Copyright © 2020 唐沈飞. All rights reserved.
//

#include <iostream>
using namespace std;

typedef char DataType;  //便于后续修改数据类型

//二叉树的结点定义
typedef struct BTNode
{
	DataType data;  //默认data域为char，可修改
	struct BTNode *lchild;  //左孩子
	struct BTNode *rchild;  //右孩子
}BTNode, *PBTNode;

//二叉树的建立
void CreateBiTree(PBTNode &T)
{
	DataType c;

	cin >> c;
	if (' ' == c)
		T = NULL;
	else
	{
		T = (PBTNode)malloc(sizeof(BTNode));
		T->data = c;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}

void Visit(PBTNode p)
{
	//cout << "comming soon!" << endl;
	cout << p->data << " "; //读取结点数据
}

//先序遍历
void preorder(PBTNode p)
{
	if (p != NULL)
	{
		Visit(p);               //先遍历根结点
		preorder(p->lchild);    //再先序遍历左子树
		preorder(p->rchild);    //再先序遍历右子树
	}
}

//中序遍历
void inorder(PBTNode p)
{
	if (p != NULL)
	{
		inorder(p->lchild);     //先中序遍历左子树
		Visit(p);               //再遍历根结点
		inorder(p->rchild);     //再中序遍历右子树
	}
}

//后序遍历
void postorder(PBTNode p)
{
	if (p != NULL)
	{
		postorder(p->lchild);   //先后序遍历左子树
		postorder(p->rchild);   //再后序遍历右子树
		Visit(p);               //再遍历根结点
	}
}

int main(int argc, const char * argv[]) {
	// insert code here...
	PBTNode p = NULL;
	CreateBiTree(p);
	preorder(p);
	cout << "Hello, World!\n";
	return 0;
}

